package com.chj.leetcode.tijie550to600;

import java.util.HashSet;
import java.util.Set;

public class Code564_FindTheClosestPalindrome2 {
//	https://developer.aliyun.com/article/328448
	public static String nearestPalindromic(String n) {
		int len = n.length();
		int num = Integer.parseInt(n);
		int res = 0;
		int minDiff = Integer.MAX_VALUE;

		Set<Integer> s = new HashSet<>();
		s.add((int) (Math.pow(10, len) + 1));
		s.add((int) (Math.pow(10, len - 1) - 1));
		String sub = n.substring(0, (len + 1) / 2);
		int prefix = Integer.parseInt(sub);
		for (long i = -1; i <= 1; ++i) {
			String pre = String.valueOf(prefix + i);
			String tail = reverse(pre);
			String str = pre + ((len & 1) == 1 ? tail.substring(1) : tail);
			s.add(Integer.parseInt(str));
		}
		s.remove(num);
		for (Integer a : s) {
			int diff = Math.abs(a - num);
			if (diff < minDiff) {
				minDiff = diff;
				res = a;
			} else if (diff == minDiff) {
				res = Math.min(res, a);
			}
		}
		return String.valueOf(res);
	}

	// https://www.cnblogs.com/grandyang/p/6915355.html
	public static String nearestPalindromic02(String n) {
		int len = n.length();
		long num = Long.parseLong(n);
		long res = 0;
		long minDiff = Long.MAX_VALUE;

		Set<Long> s = new HashSet<>();
		s.add((long) (Math.pow(10, len) + 1));
		s.add((long) (Math.pow(10, len - 1) - 1));
		String sub = n.substring(0, (len + 1) / 2);
		int prefix = Integer.parseInt(sub);
		for (long i = -1; i <= 1; ++i) {
			String pre = String.valueOf(prefix + i);
			String tail = reverse(pre);
			String str = pre + ((len & 1) == 1 ? tail.substring(1) : tail);
			s.add(Long.parseLong(str));
		}
		s.remove(num);
		for (long a : s) {
			long diff = Math.abs(a - num);
			if (diff < minDiff) {
				minDiff = diff;
				res = a;
			} else if (diff == minDiff) {
				res = Math.min(res, a);
			}
		}
		return String.valueOf(res);
	}

	public static String reverse(String str) {
		char[] chars = str.toCharArray();
		String reverse = "";
		int len = chars.length;
		for (int i = len - 1; i >= 0; i--) {
			reverse += chars[i];
		}
		return reverse;
	}

	public static void main(String[] args) {
//		String s = "691752902764181856";

		String s = "2147483647";
		String s1 = nearestPalindromic02(s);
		System.out.println(s1);
	}

}
